package main

import (
	"fmt"
)

func main() {
	arr := []int{1, 3, 4, 5, 7, 3, 2, 4}
	m := lengthOfLIS(arr)
	fmt.Println(m)
}

func lengthOfLIS(nums []int) int {
	//	边界判断
	if nums == nil || len(nums) == 0 {
		return 0
	}
	//初始化一个数组
	dp := make([]int, len(nums))
	for i := 0; i < len(nums); i++ {
		dp[i] = 1
	}

	max := 1
	for j := 1; j < len(nums); j++ {
		for m := 0; m < j; m++ {
			//	如果当前nums[m]大于nums[j],说明nums[j]可以和nums[m]结尾的上升序列构成一个新的上升序列
			if nums[m] < nums[j] {
				if dp[j] <= dp[m]+1 {
					dp[j] = dp[m] + 1
				}
				if dp[j] >= max {
					max = dp[j]
				}

			}
		}
	}
	return max
}

func printSlice(slice []int) {
	fmt.Printf("len=%d cap=%d %v\n", len(slice), cap(slice), slice)
	fmt.Println("-------------------------")
}
